<?php
/*
	Classes for linked list
	Linked list requires a lot of reference and pointer alike operations,
	which is not very straight-forward in PHP...
*/

// Class for a node inside a Binary Tree
class CLLNode {
	var $value;
	var $next;

	function __construct( $value ){
		$this->value = $value;
		$this->next = null;
	}
}

// ------------------------------------------------------
// Functions for linked lists
// ------------------------------------------------------

function ll_implode( $head ){
	if( !$head ){
		return "";
	}

	$return = "";

	$cur = $head;
	while( $cur ){
		$return .= "{$cur->value} ";	
		$cur = $cur->next;
	}	
	return $return;
}

// Insersion to a sorted ll
function ll_sort_insert( $value, &$head ){
	if( !$head ){
		$head = new CLLNode( $value );
		return true;
	}

	// Insert in front
	if( $value < $head->value ){
		$node = new CLLNode( $value );
		$node->next = $head;
		$head = $node;
		return true;
	}

	// Insert some where in the list
	$cur = $head;
	while( $cur ){
		$next = $cur->next;
		if( $value >= $cur->value ){
			if( !$next ){
				// End of the list
				$node = new CLLNode( $value );
				$cur->next = $node;
				return true;
			}
			else if( $value < $next->value ){
				// Insert between cur and next
				$node = new CLLNode( $value );
				$cur->next = $node;
				$node->next = $next;
				return true;
			}
		}

		// Go on
		$cur = $cur->next;
	}
}

// Sort the ll using ll_sort_insert
function ll_insert_sort( $head ){
	// Empty or only one node, nothing to do
	if( !$head || !$head->next ){
		return $head;
	}

	$newHead = null;
	$cur = $head;
	// Take a node from the current ll and insert to the new one
	while( $cur ){
		ll_sort_insert( $cur->value, $newHead );
		$cur = $cur->next;
	}

	return $newHead;
}

// Get the length of a ll
function ll_length( $head ){
	$length = 0;
	if( !$head ){
		return $length;
	}

	$cur = $head;
	while( $cur ){
		$length++;
		$cur = $cur->next;
	}

	return $length;
}

// LL reverse without recursion
function ll_reverse( $head, &$newHead ){
	if( !$head || !$head->next ){
		$newHead = $head;
		return;
	}

	$cur = $head;
	$next = $cur->next;
	$next_next = $next->next; // Could be null

	// Now we set the head's next node to null
	$head->next = null;

	$isDone = false;
	while ( !$isDone ){
		$next->next = $cur;
		$cur = $next;
		$next = $next_next;
		$next_next = $next->next;

		// Ending condition
		if( !$next_next ){
			// $next now is the last node or the head of the new ll
			$next->next = $cur;
			$newHead = $next;
			$isDone = true;
		}
	}
	return true;
}

// To reverse a ll:
// Asume at first node and the ll starting from the 2nd already reversed,
// Link the tail of the reversed to point to the first, set the first to point to null
// To reverse the ll starting from the 2nd already reversed is a recursive process
function ll_reverse_recursive( $head, &$newHead ){
	if( !$head ){
		return;
	}
	if( !$head->next ){
		// Tail is the new head
		$head->next = null;
		$newHead = $head;
		return;
	}
	
	$next = $head->next;
	// Get the reverse of the ll to the right
	ll_reverse_recursive( $next, $newHead );
	$next->next = $head;
	$head->next = null;

	return;
}

// Append the ll head2 after head1
function ll_append( &$head1, &$head2 ){
	// Head 1 is empty
	if( !$head1 ){
		$head1 = $head2;
		$head2 = null;
		return;
	}

	// Head 2 is empty
	if( !$head2 ){
		return;
	}

	// Traverse to tail of head 1 and append
	$tail = $head1;
	while( $tail->next ){
		$tail = $tail->next;
	}
	$tail->next = $head2;

	// Change head 2 to null
	$head2 = null;
}

// Take the head node from $src and put it in the front of $dst
function ll_move_node( &$src, &$dst ){
	if( !$src ){
		return;
	}

	$newSrc = $src->next;

	$node = $src;
	$node->next = $dst;
	
	$dst = $node;
	$src = $newSrc;
}

// Try to split a ll into two halves
// Solution 1:
// Traverse once to get the length and then traverse again to the split point
// Solution 2:
// Use two pointers to traverse, pfast moves twice the speed as pslow. 
// When pfast reaches the end of ll (null), pslow is the split point (head of the 2nd half).
// This fast, slow pointers are very classic method when dealing with ll problems.
function ll_split_half( $head, &$front, &$back ){
	// Deal with annoying corner cases first
	if( !$head || !$head->next ){
		$front = $head;
		$back = null;
		return;
	}

	$front = $head;
	$slow = $head;
	$fast = $head;
	$isDone = false;
	while( !$isDone ){
		if( $fast->next && $fast->next->next ){
			// Move forward
			$slow = $slow->next;
			$fast = $fast->next->next;
		}
		else {
			// slow is the last node of the front ll
			$back = $slow->next;
			$slow->next = null;
			$isDone = true;
		}
	}
	return;
}

// Remove duplicate nodes in a sorted ll
// Use 2 pointers, slow and fast=slow->next
// When we have slow->value == fast->value

function ll_sort_remove_duplicate( &$head ){
	if( !$head ){
		return;
	}

	$slow = $head;
	$fast = $head->next;

	$isDone = false;
	$isDuplicate = false;

	while( !$isDone ){
		if( $fast && ($fast->value == $slow->value) ){
			// Having same value
			$isDuplicate = true;
			$fast = $fast->next;
		}
		else {
			if( $isDuplicate ){
				// End of the dupilicated links
				$slow->next = $fast;	
			}

			$isDuplicate = false;

			$slow = $fast;
			if( !$fast ){
				$isDone = true;
			}
			else {
				$fast = $fast->next;
			}
				
		}
	}
}

function ll_sorted_merge( $head1, $head2 ){
	if( !$head1 ){
		return $head2;
	}
	if( !$head2 ){
		return $head1;
	}

	$cur1 = $head1;
	$cur2 = $head2;
	
	$newHead = null;
	$newTail = &$newHead;

	while( $cur1 || $cur2 ){
		if( !$cur1 ){
			ll_move_node( $cur2, $newTail );
		}
		if( !$cur2 ){
			ll_move_node( $cur1, $newTail );	
		}
		if( $cur1 && $cur2 ){
			if( $cur1->value < $cur2->value ){
				ll_move_node( $cur1, $newTail );			
			}
			else {
				ll_move_node( $cur2, $newTail );	
			}
		}

		// Because I am changing &newTail->next's value, I need a reference
		$newTail = &$newTail->next;
	}

	return $newHead;
}

// Recursion: split to halves, sort and merge back.
function ll_merge_sort( &$head ){
	if( !$head || !$head->next ){
		return;
	}

	$front = null;
	$back = null;
	ll_split_half( $head, $front, $back );
	ll_merge_sort( $front );
	ll_merge_sort( $back );
	$head = ll_sorted_merge( $front, $back );
}